/**
 * 给定数组A，可以对其中元素做两类操作：
 * 1. 除2向上取整
 * 2. 当Ai不小于K时，令Ai-=K
 * 每个元素每类操作最多进行一次，即每个元素最多进行两次操作
 * 操作1的总数不超过op1次，操作2总数不超过op2次
 * 问最后总和最小是多少。
 * 背包DP，每次决策就是做还是不做。
 * 令Dijk是前i个数，恰好进行j次操作1与k次操作2能够减少的最大值
 * 对于第i个数而言，只有4种情况，即什么都不做、只做1、只做2、以及12都做
 * 反过来Dijk由4个数决定：
 * Dijk = max(D[i-1][j][k], D[i-1][j-1][k], D[i-1][j][k-1], D[i-1][j-1][k-1])
 * 另外可以滚动优化，但是没有必要
 * 最后找到满足要求的最大值，用累加和去减即可
 */
class Solution {

using vi = vector<int>;

int K;
int N;
/// Dijk表示前i个元素j个op1、k个op2能够减少的最大值
vector<vector<vi>> D;

public:
    int minArraySum(vector<int>& nums, int k, int op1, int op2) {
        K = k;
        N = nums.size();
        D.assign(N + 1, vector<vi>(N + N + 1, vi(N + N + 1, 0)));
        D[0][0][0] = 0;

        for(int i=1;i<=N;++i){
            auto ai = nums[i - 1];
            const auto & pre = D[i - 1];
            for(int j=0;j<=i;++j){
                for(int k=0;k<=i;++k){
                    auto & d = D[i][j][k];
                    d = D[i - 1][j][k];
                    if(j >= 1 and pre[j - 1][k] != -1){ // 可以执行除2操作
                        auto tmp = pre[j - 1][k] + ai / 2;
                        if(d == -1 or tmp > d) d = tmp;
                    }
                    if(k >= 1 and ai >= K and pre[j][k - 1] != -1){
                        auto tmp = pre[j][k - 1] + K;
                        if(d == -1 or tmp > d) d = tmp;
                    }
                    if(j >= 1 and k >= 1 and pre[j - 1][k - 1] != -1 and ai >= K){
                        auto tmp = K + (ai - K) / 2; // 先减后除
                        if((ai + 1) / 2 >= K){
                            tmp = max(ai / 2 + K, tmp); // 先除后减
                        }
                        tmp += pre[j - 1][k - 1];
                        if(d == -1 or tmp > d) d = tmp;
                    }
                }
            }
        }

        // for(int i=1;i<=N;++i){
        //     printf("i = %d\n", i);
        //     for(int j=0;j<=N;++j){
        //         printf("j=%d:",j);
        //         for(int k=0;k<=N;++k){
        //             printf("%4d", D[i][j][k]);
        //         }
        //         printf("\n");
        //     }            
        // }

        int ans = 0;
        for(int j=0;j<=op1;++j)for(int k=0;k<=op2;++k){
            if(D[N][j][k] == -1) continue;
            ans = max(ans, D[N][j][k]);
        }
        return accumulate(nums.begin(), nums.end(), 0) - ans;
    }

};